package LineCode.剑指Offer.举例让抽象具体化;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 */
public class 二叉搜索树的后序遍历序列 {

    public static void main(String[] args) {

    }

    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length <= 0)
            return false;
        if (sequence.length == 1)
            return true;
        return isBST(sequence, 0, sequence.length-1);
    }

    public boolean isBST(int[] sequence, int start, int end) {
        if (start >= end) return true;
        int head = sequence[end];
        int splitNum = 0;
        for (int i = 0; i < end && sequence[i] < head; i++, splitNum++);
        for (int i = splitNum; i < end; i++) {
            if (sequence[i] < head)
                return false;
        }
        return isBST(sequence, start, splitNum-1) && isBST(sequence, splitNum, end-1);

    }
}
